package offer.zixing.chapter07;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 请实现如下类型RecentCounter，它是统计过去3000毫秒内的请求次数的计数器。
 * 该类型的构造函数RecentCounter()初始化计数器，
 * 请求数为0；函数ping(int t)在在时间t添加一个新请求（t表示以毫秒为单位的时间），
 * 并返回过去3000毫秒内（时间范围为[t-3000, t]）发生的所有请求数。
 * 假设每次调用函数ping时参数t都比之前调用时的参数值大。
 *
 * class RecentCounter {
 *     public RecentCounter();
 *     public int ping(int t);
 * }
 *
 * 例如，在初始化一个RecentCounter计数器之后，ping(1)的返回值是1，因为时间范围[-2999, 1]只有1个请求；
 * ping(10)的返回值是2，因为时间范围[-2990, 10]有2个请求；ping(3001)的返回值是3，因为时间范围[1, 3001]有3个请求；
 * ping(3002)的是3，因为时间范围[2, 3002]只有两个请求，发生在时间1的请求已经不在这个时间范围了。
 */
public class Test042 {

    public static void main(String[] args) {
        RecentCounter recentCounter = new RecentCounter();
        System.out.println("ping : " + recentCounter.ping(1));
        System.out.println("ping : " + recentCounter.ping(10));
        System.out.println("ping : " + recentCounter.ping(3001));
        System.out.println("ping : " + recentCounter.ping(3002));
        System.out.println("ping : " + recentCounter.ping(6003));
    }

    static class RecentCounter {
        private Queue<Integer> times;
        private int windowSize;

        public RecentCounter() {
            times = new LinkedList<>();
            windowSize = 3000;
        }

        public int ping(int t) {
            // 加入队列
            times.offer(t);
            // 循环遍历之前的元素超过 windowSize 时，出列
            // peek() 最先入列的元素
            while (times.peek() < t - windowSize) {
                times.poll();
            }
            return times.size();
        }
    }
}
